Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Improved artificial bee colony algorithm based on P system for 0-1 knapsack problem
SONG Xiaoxiao, WANG Jun
Journal of Computer Applications    2015, 35 (7): 2088-2092.   DOI: 10.11772/j.issn.1001-9081.2015.07.2088
Abstract562)      PDF (726KB)(516)       Save

Aiming at the defects of resolving large scale 0-1 knapsack problem with existed algorithm, an Improved Artificial Bee Colony algorithm based on P Systems (IABCPS) was introduced in this paper. The idea of Membrane Computing (MC), polar coordinate coding and One Level Membrane Structure (OLMS) was used by IABCPS. Evolutionary rules of improved Artificial Bee Colony (ABC) algorithm and transformation or communication rules in P systems were adopted to design its algorithm. The limit of number of trials "limit" was adjusted to keep the balance of exploitation and exploration. The experimental results show that IABCPS can find the optimum solutions in solving small scale knapsack problems. In solving a knapsack problem with 200 items, compared with Clonal Selection Immune Genetic Algorithm (CSIGA), IABCPS increases the average results by 0.15% and decreases variance by 97.53%; compared with ABC algorithm, IABCPS increases the average results by 4.15% and decreases variance by 99.69%. The results demonstrate that IABCPS has good ability of optimization and stability. Compared with Artificial Bee Colony algorithm based on P Systems (ABCPS) in solving large scale knapsack problem with 300, 500, 700 and 1000 items respectively, IABCPS increases the average results by 1.25%,3.93%,6.75% and 11.21%, and the ratio of the variance and the number of experiments keeps in single digits. It shows its strong robustness.

Reference | Related Articles | Metrics